package chapter6;

/**
 * 计算联通分量的方式就是深度优先遍历
 *
 * @author yuh
 * @date 2018/4/26 13:10
 */
public class FloodFill {

    static boolean[][] signed;
    static int[][] d = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    static int getChunks(char[][] chars) {
        int count = 0;
        signed = new boolean[chars.length][chars[0].length];
        for (int i = 0; i < signed.length; i++) {
            for (int j = 0; j < signed[i].length; j++) {
                signed[i][j] = false;
            }
        }
        for (int i = 0; i < chars.length; i++) {
            for (int j = 0; j < chars[i].length; j++) {
                if (inArea(i, j, chars.length, chars[0].length) && chars[i][j] == '1' && !signed[i][j]) {
                    floodFill(chars, i, j);
                    count++;
                }
            }
        }

        return count;
    }

    private static void floodFill(char[][] chars, int i, int j) {
        signed[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int newX = i + d[k][0];
            int newY = j + d[k][1];
            if (inArea(newX, newY, chars.length, chars[0].length) && chars[newX][newY] == '1' && !signed[newX][newY]) {
                floodFill(chars, newX, newY);
            }
        }
    }


    private static boolean inArea(int newX, int newY, int length, int length1) {
        return newX > -1 && newY > -1 && newX < length && newY < length1;
    }

    public static void main(String[] args) {
        char[][] chars = {{'1', '1', '1'}, {'1', '0', '1'}, {'1', '0', '1'}, {'1', '0', '1'}};
        System.out.println(getChunks(chars));
    }
}
